package com.njupt.twoStage.BinarySearch;

import java.util.Arrays;
import java.util.Scanner;

public class TernarySearch {

    public int ternarySearch(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;

        while (left <= right) {
            int mid1 = left + (right - left) / 3;
            int mid2 = right - (right - left) / 3;

            if (array[mid1] == target) {
                return mid1;
            }

            if (array[mid2] == target) {
                return mid2;
            }

            if (target < array[mid1]) {
                right = mid1 - 1;
            } else if (target > array[mid2]) {
                left = mid2 + 1;
            } else {
                left = mid1 + 1;
                right = mid2 - 1;
            }
        }

        return -1; // 目标值不在数组中
    }

    public static void main(String[] args) {
        TernarySearch test = new TernarySearch();
        int[] nums = {1,5,9,11,13,15,16,18};
        System.out.println("输出的有序数组为：" + Arrays.toString(nums));
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入要查找的target数");
        int target = sc.nextInt();

        int location = test.ternarySearch(nums, target);
        if(location!=-1){
            System.out.println(target + "位于有序数组的"+ location);
        }else{
            System.out.println(target + "查找失败"+ location);
        }

    }
}
